
package jdd.graph;

import jdd.util.*;

import java.util.*;
import java.io.*;

import javax.xml.parsers.*;
import org.xml.sax.*;
import org.xml.sax.helpers.*;


/**
 * some procedures to load/save graphs:
 * 1. load/saveEdgeList
 * 2. load/saveDIMACS
 * 3. load/saveXML
 *
 */


public class GraphIO {
	// -------------------------------------------------------------------------------

	/** save edge-list, an entry  "u v w" per line */
	public static void saveEdgeList(Graph g, String filename) {
		try {
			PrintStream ps = new PrintStream( new FileOutputStream(filename));
			ps.println("# Generated by jdd.graph.GraphIO.saveEdgeList()");

			for (Enumeration e = g.getEdges().elements() ; e.hasMoreElements() ;) {
				Edge n = (Edge) e.nextElement();
				ps.println(n.n1.getLabel() + "\t" + n.n2.getLabel() + "\t" + n.weight);
			}
			ps.flush();
			ps.close();
		} catch(IOException exx) {
			JDDConsole.out.println("Unable to save graph to " + filename + ":" + exx);
		}
	}

	// -------------------------------------------------------------------------------

	/** create graph from edge-list */
	public static Graph loadEdgeList(String filename) {
		try {
			BufferedReader br = new BufferedReader( new FileReader(filename) );
			WeightedGraph wg = new WeightedGraph();
			HashMap hm = new HashMap();
			while(br.ready()) {
				String line = br.readLine();
				if(line != null && line.length() > 0 && line.charAt(0) != '#') {
					StringTokenizer st = new StringTokenizer(line, "\t ");
					String str1 = st.nextToken();
					String str2 = st.nextToken();
					String str3 = st.nextToken();
					if(str3 != null) {
						double weight = Double.parseDouble(str3);
						Node n1 = (Node) hm.get(str1);
						Node n2 = (Node) hm.get(str2);
						if(n1 == null) {
							n1 = wg.addNode();
							n1.setLabel(str1);
							hm.put(str1,n1);
						}
						if(n2 == null) {
							n2 = wg.addNode();
							n2.setLabel(str2);
							hm.put(str2, n2);
						}
						wg.addEdge(n1,n2,weight);
					} else {
						JDDConsole.out.println("BAD line: '"+line +"'");
						br.close();
						return null;
					}
				}
			}
			br.close();
			return wg;
		} catch(IOException exx) {
			JDDConsole.out.println("Unable to load graph from " + filename + ":" + exx);
		}
		return null;
	}

	// -------------------------------------------------------------------------------
	/** save graph in DIMACS format. NOTE: alters Node.extra1 !!! */
	public static void saveDIMACS(Graph g, String filename) {

		try {
			PrintStream ps = new PrintStream( new FileOutputStream(filename));
			ps.println("c Generated by jdd.graph.GraphIO.saveDIMACS()");
			ps.println("p edge " + g.numOfNodes() + " " + g.numOfEdges() );


			int node_count = 0;
			for (Enumeration e = g.getNodes().elements() ; e.hasMoreElements() ;) {
				Node n2 = (Node) e.nextElement();
				n2.extra1 = node_count++;
				// ps.println("v " + node_count + " " + n2.weight);
			}



			for (Enumeration e = g.getEdges().elements() ; e.hasMoreElements() ;) {
				Edge n = (Edge) e.nextElement();
				ps.println("e " + (1 + n.n1.extra1) + " " + (1 + n.n2.extra1) );
			}
			ps.flush();
			ps.close();
		} catch(IOException exx) {
			JDDConsole.out.println("Unable to save graph to " + filename + ":" + exx);
		}

	}

	// -------------------------------------------------------------------------------
	/** load graph from ASCII DIMACS format */
	public static Graph loadDIMACS(String filename) {
		try {
			BufferedReader br = new BufferedReader( new FileReader(filename) );
			Graph g = new Graph(false);
			boolean first = true;
			Node [] nodes = null;

			while(br.ready()) {
				String line = br.readLine();
				if(line != null && line.length() > 0 && line.charAt(0) != 'c') {

					StringTokenizer st = new StringTokenizer(line, "\t ");
					String str1 = st.nextToken();

					if(str1.equals("p") && first) {
						String str2 = st.nextToken(); // FORMAT
						String str3 = st.nextToken(); // NODES
						int num_nodes = Integer.parseInt( str3);
						nodes = new Node[num_nodes];
						for(int i = 0; i < num_nodes; i++) nodes[i] = g.addNode();
						first = false;
					} else if(str1.equals("v") && !first) {
						// ignore
						// int id = Integer.parseInt( st.nextToken());
						// nodes[id-1] = g.addNode();
					} else if(str1.equals("e") && !first) {
						int v = Integer.parseInt( st.nextToken());
						int w = Integer.parseInt( st.nextToken());
						g.addEdge( nodes[v-1], nodes[w-1]);

					} else JDDConsole.out.println("warning: ignoring line '" +  line + "'");
				}
			}
			br.close();
			return g;
		} catch(IOException exx) {
			JDDConsole.out.println("Unable to load graph from " + filename + ":" + exx);
		}
		return null;
	}



	// -------------------------------------------------------------------------------
	/** load graph from binary DIMACS format */
	public static Graph loadBinaryDIMACS(String filename) {
		try {
			BufferedReader br = new BufferedReader( new FileReader(filename) );
			Graph g = new Graph(false);

			String line = br.readLine();
			int skip = Integer.parseInt(line);
			do {line = br.readLine();} while(line.charAt(0) != 'p');

			StringTokenizer st = new StringTokenizer(line, "\t ");

			Test.check(st.nextToken().equals("p"), "not DIAMCS format (need 'p ...')");
			Test.check(st.nextToken().equals("edge"), "not DIAMCS format (need 'p edge ...')");

			int nodeC = Integer.parseInt( st.nextToken());
			int edgeC = Integer.parseInt( st.nextToken());

			Node [] nodes = new Node[nodeC];
			for(int i = 0; i < nodeC; i++) nodes[i] = g.addNode();


			br.close();
			InputStream is = new FileInputStream(filename);
			while( is.read() != '\n') ; // sip the first line
			is.skip(skip);
			// JDDConsole.out.println("nodes = " + nodeC + ", edges = " + edgeC);

			BitStream bs = new BitStream(is);






			int eee = 0;
			for(int i = 0; i < nodeC; i++){
				for(int j = 0; j < i; j++) {
					if(bs.next()) {
						g.addEdge( nodes[i], nodes[j]);
					}
				}
				bs.next(); // the DIMACS stupid format bug in the first round (i = 0)
				bs.skipByte();
			}

			if(g.numOfEdges() * 2 != edgeC) {
				JDDConsole.out.println("File '"+filename+"'probably corrupted, expected " + edgeC + " edges, found " + (2 * g.numOfEdges()) );
			}
			return g;
		} catch(IOException exx) {
			JDDConsole.out.println("Unable to load graph from " + filename + ":" + exx);
		}
		return null;
	}



	// -------------------------------------------------------------------------------
	/** save graph in XML */
	public static void saveXML(Graph g, String filename) {

		try {
			PrintStream ps = new PrintStream( new FileOutputStream(filename));
			ps.println("<?xml version=\"1.0\" encoding=\"ISO-8859-1\"?>");
			ps.println("\t<graph directed=\"" + (g.isDirected() ? 1 : 0 ) +"\">");


			ps.println("\t\t<nodes>");
			for (Enumeration e = g.getNodes().elements() ; e.hasMoreElements() ;) {

				Node n2 = (Node) e.nextElement();
				ps.print("\t\t\t<node id=\"" + n2.id + "\" label=\"" + n2.getLabel()
					+ "\" flags=\"" + n2.flags + "\" ");
				ps.println("/>");
			}
			ps.println("\t\t</nodes>");


			ps.println("\t\t<edges>");
			for (Enumeration e = g.getEdges().elements() ; e.hasMoreElements() ;) {
				Edge n = (Edge) e.nextElement();
				ps.print("\t\t\t<edge from=\"" + n.n1.id + "\" to=\"" + n.n2.id + "\" " +
							" weight=\"" + n.weight + "\"" +
							" label=\"" + n.getLabel() + "\"" +
							" flags=\"" + n.flags + "\" ");
				ps.println("/>");
				// ps.println("e " + (1 + n.n1.extra1) + " " + (1 + n.n2.extra1) );
			}
			ps.println("\t\t</edges>");
			ps.println("\t</graph>");
			ps.flush();
			ps.close();
		} catch(IOException exx) {
			JDDConsole.out.println("Unable to save graph to " + filename + ":" + exx);
		}
	}

	// -------------------------------------------------------------------------------

	/** load graph from XML format */
	public static Graph loadXML(String filename) {
		try {
			// SAXParser saxp = SAXParserFactory.newInstance().newSAXParser();
			SAXParser saxp = XMLHelper.getParser();
			GraphXMLHandler handler = new GraphXMLHandler();
			saxp.parse( new File(filename), handler);
			return handler.g;

		} catch(Exception exx) { // IO, ParserConfiguration and SAX exceptions
			JDDConsole.out.println("Unable to load graph from " + filename + ":" + exx);
		}
		return null;
	}


	// -------------------------------------------------------------------------------

	/** testbench. do not call */
	public static void internal_test() {
		Test.start("GraphIO");

		Graph g = loadEdgeList("data/c3.pcg");
		Test.checkEquality(g.numOfNodes(), 53, "nodes in c3.pcg");
		Test.checkEquality(g.numOfEdges(), 246, "edges in c3.pcg");

		saveDIMACS(g, "data/c3.DIMACS");
		Graph g2 = loadDIMACS("data/c3.DIMACS");
		Test.checkEquality(g2.numOfNodes(), 53, "nodes in c3.DIMACS");
		Test.checkEquality(g2.numOfEdges(), 246, "edges in c3.DIMACS");
		FileUtility.delete("data/c3.DIMACS");	// cleanup:

		saveXML(g2,"data/c3.xml");
		Graph g3 = loadXML("data/c3.xml");
		Test.checkEquality(g3.numOfNodes(), 53, "nodes in c3.xml");
		Test.checkEquality(g3.numOfEdges(), 246, "edges in c3.xml");
		FileUtility.delete("data/c3.xml");	// cleanup:
		Test.end();
	}
}




// -------------------------------------------------------------------------------
/** internal class for loading XML stuff */
/* package */ class GraphXMLHandler extends DefaultHandler {
	private static final int
		STATE_NONE = 0, STATE_DOCUMENT = 1, STATE_GRAPH = 2, STATE_NODES = 3, STATE_EDGES = 4;
	private int state = STATE_NONE;

	/* package */ WeightedGraph g = null;
	private HashMap nodemap = new HashMap();

	public void endElement(String uri, String localName, String qName)  {
		if(qName.equals("Document")) {
			if(state == STATE_DOCUMENT) state = STATE_NONE;

		} else if(qName.equals("graph")) {
			if(state == STATE_GRAPH) state = STATE_DOCUMENT;

		} else if(qName.equals("nodes")) {
			if(state == STATE_NODES) state = STATE_GRAPH;
		} else if(qName.equals("edges")) {
			if(state == STATE_EDGES ) state = STATE_GRAPH;
		}
	}

	public void startElement(String uri, String localName, String qName, Attributes attributes) {
		if(qName.equals("Document")) {
			if(state == STATE_NONE) state = STATE_DOCUMENT;

		} else if(qName.equals("graph")) {
			if(state == STATE_DOCUMENT || state == STATE_NONE) state = STATE_GRAPH; else return;

			boolean directed = false;
			String str = attributes.getValue("directed");
			if(str != null &&str.equals("1")) directed  = true;
			g = new WeightedGraph(directed);

		} else if(qName.equals("nodes")) {
			if(state == STATE_GRAPH) state = STATE_NODES;

		} else if(qName.equals("node")) {
			if(state != STATE_NODES) return;

			String id= attributes.getValue("id");
			String label= attributes.getValue("label");
			String flags= attributes.getValue("flags");
			Node n = g.addNode();
			n.setLabel(label);
			n.flags = Integer.parseInt(flags);
			nodemap.put(id, n);

		} else if(qName.equals("edges")) {
			if(state == STATE_GRAPH) state = STATE_EDGES;

		} else if(qName.equals("edge")) {
			if(state != STATE_EDGES) return;

			String from  = attributes.getValue("from");
			String to    = attributes.getValue("to");
			String label = attributes.getValue("label");
			String flags = attributes.getValue("flags");
			String weight = attributes.getValue("weight");

			Edge e = g.addEdge( (Node)nodemap.get(from),(Node)nodemap.get(to), Double.parseDouble(weight) );
			e.flags = Integer.parseInt(flags);;
		}
	}
}
